package com.zlk.algorithm.dataStructure.tree.treeDp;

import com.zlk.algorithm.dataStructure.tree.TreeNode;

/**
 * @program: algorithm
 * @ClassName MaxSubBSTHead
 * @description:给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点
 * @author: slfang
 * @create: 2024-02-21 13:54
 * @Version 1.0
 **/
public class MaxSubBSTHead {

    //可能性
    //   经过 x
    //   不经过 Math.max(左数，右树)
    //信息:
    //    size, isBst，max ,min


    class Info {
        int size;
        boolean isBst;
        int max ;
        int min;
        int maxSize;
        TreeNode maxNode;

        public Info(int size, boolean isBst, int max, int min,int maxSize,TreeNode maxNode) {
            this.size = size;
            this.isBst = isBst;
            this.max = max;
            this.min = min;
            this.maxSize = maxSize;
            this.maxNode = maxNode;
        }
    }

    private int largestBSTSubtree(TreeNode head) {
        if(head==null){
            return 0;
        }
        return process(head).maxSize;
    }

    public Info process(TreeNode node){
        if(node == null){
            return null;
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int size = 1;
        boolean isBst = true;
        int max = node.value ;
        int min = node.value;
        int maxSize = 1;
        if(leftInfo !=null){
            if( leftInfo.max>=node.value){
                isBst = false;
            }
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
            if(!leftInfo.isBst){
                isBst = false;
            }
            size+= leftInfo.size;
        }
        if(rightInfo !=null){
            if(rightInfo.min<=node.value){
                isBst = false;
            }
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min);
            if(!rightInfo.isBst){
                isBst = false;
            }
            size+= rightInfo.maxSize;
        }
        TreeNode maxNode = node;
        if(isBst){
            //经过x
            maxSize = size;
            maxNode = node;
        }else{
            //不经过
            if(leftInfo!=null){
                maxSize = Math.max(leftInfo.maxSize,maxSize);
                maxNode = leftInfo.maxSize>maxSize?leftInfo.maxNode:maxNode;
            }
            if(rightInfo!=null){
                maxSize = Math.max(rightInfo.maxSize,maxSize);
                maxNode = rightInfo.maxSize>maxSize?rightInfo.maxNode:maxNode;
            }
        }
        return new Info(size,isBst,max,min,maxSize,maxNode);
    }

}
